COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00005 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A85.Tex[254,rwf]\today}
\leftline{\copyright Robert W. Floyd, January 30, 1989}
\leftline{\sevenrm Unpublished Draft}
\bigskip
[Rough draft of theorem on D1CLs]
\bigskip
Let $L$ be a language.  Let $e↓n$ be the number of distinct prefix equivalence
classes of prefixes of length $n$.  We show if $e↓n/n$ is unbounded, no
D1CA accepts $L$.  Suppose some D1CA does accept $L$.

Consider a typical computation that accepts a string $xy$ where $\left |x\right| 
= n$.
Let $c↓i$ be the configuration at which the counter first reaches $i$.  For
$i < j$, the input and control states of $c↓i$ and $c↓j$ can not be
the same, or the program would run forever.  Therefore while reading $x$, a 
program with $q$ control states can count to no more than $q(n+1)$, and can 
reach no more than $q↑2(n+1)$ storage configurations.

Choose $n$ for which $e↓n> q↑2(n+1)$.  By the pigeonhole principle,
there are prefixes $x↓1$, $x↓2$ of length $n$, $x↓1 \not\sim x↓2$, for
which the program reaches the same configuration while scanning $x↓1$
and $x↓2$.  Since $x↓1 \not\sim x↓2$, there is a string $y$ for which 
$x↓1 y\in L$, $x↓2 y \notin L$ (or vice versa).
But the computation that accepts $x↓1y$ can be modified into one that
accepts $x↓2y$, contrary to the assumption that the D1CA accepts $L$.

The above readily shows that the languages $\{x x\}$, $\{x \, \hbox {reverse}(x)\}$,
$\{a↑ib↑jc↑jd↑i\}$, $\{a↑ib↑jc↑id↑j\}$, and their complements are not
accepted by D1CLs.  The complements, however, are accepted by N1CLs, 
so the above argument does
not apply to nondeterministic programs.
\end